﻿#include "unit_test.h"
#include <stack>
#include <deque>
#include <cassert>

namespace code_01_02
{
    // public方便测试
    static void transfer(std::stack<int>& from, std::stack<int>& to)
    {
        while (!from.empty())
        {
            int top = from.top();
            from.pop();
            to.push(top);
        }
    }

    TEST(Transfer)
    {
        std::stack<int> from({ 1, 2, 3 });
        std::stack<int> to;
        std::stack<int> expected({ 3, 2, 1 });
        transfer(from, to);
        // unit_test功能有限，只能这么写
        ASSERT_EQ(true, to == expected);
    }

    namespace code_01_02_v1
    {
        /**
         * 不变式：s1_始终是入队序列，s2_始终为空
         * 缺点：每次都要在s1_和s2_之间来回拷贝两次数据，效率有点低
         */
        class StackQueue
        {
        public:
            void add(int i)
            {
                s1_.push(i);
            }

            int peek() const
            {
                assert(!s1_.empty());
                assert(s2_.empty());
                transfer(s1_, s2_);
                int result = s2_.top();
                transfer(s2_, s1_);
                return result;
            }

            int poll()
            {
                assert(!s1_.empty());
                assert(s2_.empty());
                transfer(s1_, s2_);
                int result = s2_.top();
                s2_.pop();
                transfer(s2_, s1_);
                return result;
            }

        private:
            mutable std::stack<int> s1_;
            mutable std::stack<int> s2_;
        };
    }

    namespace code_01_02_v2
    {
        /**
         * 减少拷贝
         */
        class FastStackQueue
        {
        public:
            void add(int i)
            {
                s1_.push(i);
            }

            int peek() const
            {
                assert(!s1_.empty() || !s2_.empty());
                if (s2_.empty())
                {
                    transfer(s1_, s2_);
                }
                return s2_.top();
            }

            int poll()
            {
                int result = peek();
                assert(!s2_.empty());
                s2_.pop();
                return result;
            }

        private:
            mutable std::stack<int> s1_;
            mutable std::stack<int> s2_;
        };
    }

    template <typename Queue>
    void StackQueueTest()
    {
        Queue q;

        // add 1 2
        q.add(1);
        ASSERT_EQ(1, q.peek());
        q.add(2);
        ASSERT_EQ(1, q.peek());

        // poll 1 2
        ASSERT_EQ(1, q.poll());
        ASSERT_EQ(2, q.poll());
    }

    TEST(StackQueue)
    {
        StackQueueTest<code_01_02_v1::StackQueue>();
        StackQueueTest<code_01_02_v2::FastStackQueue>();
    }
}
